package dynamicprogramming.三步问题;

//三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模100
//0000007。
//
// 示例1:
//
//
// 输入：n = 3
// 输出：4
// 说明: 有四种走法
//
//
// 示例2:
//
//
// 输入：n = 5
// 输出：13
//
//
// 提示:
//
//
// n范围在[1, 1000000]之间
//
// Related Topics 动态规划
// 👍 45 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /*
     *思路：其实以第N阶楼梯为例，到达N的次数为f（N）=f（N-1）+f(N-2)+f(N-3)，所以这里就是动态转移方程
     *     利用递归的话，因为数比较大所以时间消耗会非常大。所以这里用动态规划，有题目可知到f(1)=1,f(2)=2,f(3)=4
     *
     *
     *     得到这个方程很常规,但是最坑的地方在于溢出问题,这也是为什么题目提示对1000000007取模.
     *     经过测试,在n = 41-42这个节点发生了反转,也就是说在41用上述转移方程的时候,还是正常的,
     *     但是到了42就不行了.究其原因,在于41-42之间的数发生了一溢出,考虑到如果dp[n-2]+dp[n-1]可能优先溢出,
     *     也就是说dp[n-3]也许还未溢出,但是接下来就有可能溢出了,所以需要稍微调整一下状态转移方程
     *     f[i] = ((f[i - 1] +f[i - 2] )%1000000007+ f[i - 3]) % 1000000007;
     */
    public int waysToStep(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        int[] f = new int[n + 1];
        f[1] = 1;
        f[2] = 2;
        f[3] = 4;
        for (int i = 4; i <= n; i++)
            f[i] = ((f[i - 1] +f[i - 2] )%1000000007+ f[i - 3]) % 1000000007;
        return f[n] % 1000000007;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

